package main.old.new_2023.last.month_6;

import main.dataStruct.TreeNode;

/**
 * @Description:
 * todo 剑指 Offer 28. 对称的二叉树
 * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。\
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 * todo 剑指 Offer 12. 矩阵中的路径
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母不允许被重复使用。
 * todo 剑指 Offer 13. 机器人的运动范围
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
 * 一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
 * 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，
 * 因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/
public class Solution0628 {

    //机器人的运动范围
    int m, n, k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        this.m = m; this.n = n; this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }
    public int dfs(int i, int j, int si, int sj) {
        if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }


    //计算每位数字加起来
    int sums(int x){
        int s = 0;
        while(x != 0) {
            s += x % 10;
            x = x / 10;
        }
        return s;
    }



    //矩阵中的路径
    public boolean exist(char[][] board, String word) {
        //递归找到合适的字母
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board,char[] words,int i,int j,int k){
        //判断边界和字母是否相等
        if (i < 0|| j<0 || i>board[0].length-1 || j > board.length-1 || board[i][j] !=words[k] ){
            return false;
        }
        //判断是否完成word
        if (k == words.length-1){
            return true;
        }
        //将所在字母置空，避免重复
        board[i][j] ='\0';
        //将左右
        boolean res = dfs(board, words, i + 1, j, k + 1) || dfs(board, words, i - 1, j, k + 1) ||
                dfs(board, words, i, j + 1, k + 1) || dfs(board, words, i , j - 1, k + 1);
//        board[i][j] = words[k];
        return res;
    }

    //对称的二叉树
    public boolean isSymmetric(TreeNode root) {
        //使用递归的思想，左边等于右边，右边等于左边，向下递归，如果值不相等或者其中一个是null，另一个不是，那就是false
        if (root == null){
            return true;
        }
        return compare(root.left,root.right);
    }
    boolean compare(TreeNode left,TreeNode right){
        if (left == null && right ==  null){
            return true;
        }
        if (  left == null || right == null || left.val!= right.val){
            return false;
        }
        return compare(left.left,right.right) && compare(left.right,right.left);
    }

}
